package solution;

import java.util.*;


/*
* 20
* */
public class IsValid {
    /*
    * 使用栈 + 哈希表
    * */
    public boolean solution1(String s) {
        int n = s.length();
//        if (n % 2 == 1){
//            return false;
//        }
//
//        Map<Character, Character> pairs = new HashMap<Character, Character>(){{
//            put(')', '(');
//            put(']','[');
//            put('}', '{');
//        }};
//
//        Deque<Character> stack = new LinkedList<>();
//        for (int i = 0 ; i < n ; i++){
//            char ch = s.charAt(i);
//            if (pairs.containsKey(ch)){
//                if (stack.isEmpty() || stack.peek() != pairs.get(ch)){
//                    return false;
//                }
//                stack.pop();
//            }else {
//                stack.push(ch);
//            }
//        }
//        return stack.isEmpty();

        if (s != null && s.length() != 0 && s.length() % 2 == 0){
            Map<Character, Character> hashMap = new HashMap<Character, Character>(){
                {
                    put(')','(');
                    put(']', '[');
                    put('}', '{');
                }
            };

            Stack<Character> stack = new Stack<>();
            for (char c : s.toCharArray()){
                if (!hashMap.containsKey(c)){
                    stack.push(c);
                }else {
                    if (stack.isEmpty() || stack.peek() != hashMap.get(c)){
                        return false;
                    }
                    stack.pop();
                }
            }

            return stack.isEmpty();
        }

        return false;
    }



    //使用栈
    public boolean solution2(String s){
//        Stack<Character> stack = new Stack<>();
//        for (int i = 0 ; i < s.length() ; i++){
//            char c = s.charAt(i);
//            if (c == '(' || c == '[' || c == '{'){
//                stack.push(c);
//            }else if (stack.empty()){
//                return false;
//            } else if (c == ')' && stack.pop() != '('){
//                return false;
//            }else if (c == ']' && stack.pop() != '['){
//                return false;
//            }else if (c == '}' && stack.pop() != '{'){
//                return false;
//            }
//        }
//        return stack.isEmpty();

        if (s != null && s.length() != 0 && s.length() % 2 == 0){
            Stack<Character> stack = new Stack<>();
            for (char c : s.toCharArray()){
                if (c == '(' || c == '{' || c == '[') {
                    stack.push(c);
                }else if (stack.isEmpty()){
                    return false;//防止"]"这种测试用例
                }else if (c == ')' && stack.pop() != '('){
                    return false;
                }else if (c == ']' && stack.pop() != '['){
                    return false;
                }else if (c == '}' && stack.pop() != '{'){
                    return false;
                }
            }
            return stack.isEmpty();
        }

        return false;
    }

    /*
    * 使用循环
    * */
    public boolean solution3(String s) {
        int length = 0;
        do {
            length = s.length();
            s = s.replace("()", "")
                    .replace("{}", "")
                    .replace("[]", "");
        }while (length != s.length());

        return s.length() == 0;
    }

    /*
    * 使用ASCII码的特性
    * */
    public boolean solution4(String s) {
//        char[] arr = s.toCharArray();
//        Stack stack = new Stack();
//        for (char ch : arr){
//            if (stack.empty()){
//                stack.push(ch);
//            }else {
//                char top = (char)stack.lastElement();
//                if (ch - top == 1 || ch - top == 2){
//                    stack.pop();
//                }else {
//                    stack.push(ch);
//                }
//            }
//        }
//
//        return stack.isEmpty();

        if (s != null && s.length() != 0 && s.length() % 2 == 0){
            Stack<Character> stack = new Stack<>();
            for (Character c : s.toCharArray()){
                if (stack.isEmpty()){
                    stack.push(c);
                }else {
                    char top = (char) stack.lastElement();
                    if (c - top == 1 || c - top == 2 ){
                        stack.pop();
                    }else {
                        stack.push(c);
                    }
                }
            }
            return stack.isEmpty();
        }

        return false;
    }
}
